The objective of this phase I/II study is to determine the maximum tolerated dose of taxol in combination with carboplatin in previously untreated patients with advanced or recurrent Non Small Cell Lung Cancer (NSCLC); define the pharmacokinetics of carboplatin with combination therapy, and correlate 24 hour total plasma platinum concentration and pharmacodynamic consequences of therapy with the AUC of carboplatin.